package 每日一题;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 547. 省份数量
 */
public class Date0107 {

    /**
     * 自解：利用广度优先遍历 pro存储省份数量 isVisited存储是否走过
     * 一个队列用来进行广度优先
     * @param isConnected
     * @return
     */
    public int findCircleNum(int[][] isConnected) {
        int provs = isConnected.length;
        Queue<Integer> queue = new LinkedList<>();
       boolean[] isVisited = new boolean[provs];
       int proNUm =0;

        for (int i=0;i<provs;i++){
            if (!isVisited[i]){
                queue.add(i);

                while (!queue.isEmpty()){
                    int temp = queue.poll();
                    isVisited[temp] = true;
                    for (int j= 0;j<provs;j++){
                            if (isConnected[temp][j]==1 && !isVisited[j]){
                                queue.add(j);
                            }
                    }
                }
                proNUm++;
            }

        }

        return proNUm;

    }

}
